COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	multi.pro[s83,jmc]	Proposal for research in multi-processing LISP
C00007 ENDMK
C⊗;
multi.pro[s83,jmc]	Proposal for research in multi-processing LISP

	John McCarthy and Richard Gabriel propose to continue their
exploration of how to use multi-processor systems effectively for
LISP computation.  The planned multi-processor VAX will be a suitable
vehicle for this work.

	The idea to be investigated is described in some detail in
Appendix A where it is focussed on the S-1 computer being developed
at Lawrence Livermore National Laboratory.  However, the resources
personnel available for doing the work at Livermore are limited,
four processors is better than two, getting a usable system on
the VAX is of more general interest, and there are more people
at Stanford - both to do the work and to use the system.  Therefore,
we think it will be valuable to explore multi-processing on the VAX
and for the McCarthy-Gabriel approach to interact with the other
work on multi-processing described in this proposal.

	As described in Appendices A and B, there are several
approaches to getting good performance on single problems from
multi-processor computers.  One is to have a compiler take into
account the number of processors and produce an object program
that suitably divides up the work.  The idea we intend to explore
is to produce a run-time program that doesn't depend on any
specific number of processors being available.  When it comes
to parts of the program that can be done in parallel it creates
or extends a queue of tasks.  When processors finish tasks they
take new ones from the queue.  This system tolerates changes
in the number of available processors occurring at run time.

	We propose to accomplish the following tasks and
explore the following problems.

	1. Develop a working system for the multi-processor VAX
adapted from a portable Common LISP.

	2. Experiment with control of when multi-processing should
be allowed.  Since multi-processing involves overhead and the
maintenance of queues, it seems that it should be done only enough
to keep all the available processors busy.
In particular, short sequences of instructions should not be
multi-processed, because then the overhead of controlling the
multi-processing may dominate the actual computation.

	3. We will explore how the control of queuing should be divided
between the object program and the operating system.  Appendix A
discusses mult-processing in LISP including addtional language
constructs, and Appendix B discusses the general problem of
multi-processing operating systems.  Because of the short time
available for preparing this proposal we haven't purged the S-1
specific considerations from these appendices.  However almost
all of the considerations apply in general.